import Node from './models/node';
import { ICompareFunction, defaultCompare, Compare } from '../util';

/**
 * 二叉搜索树，只允许在左侧节点存储比父节点小的值，在右侧节点存储比父节点大的值
 * 大量用了递归方法，二叉搜索树的删除方法是难点
 */
export default class BinarySearchTree<T> {
    protected _root: Node<T> = null;
    protected _compareFn: ICompareFunction<T>;
    constructor(compareFn: ICompareFunction<T> = defaultCompare) {
        this._compareFn = compareFn;
    }
    /**
     * 向树中插入一个新的键
     */
    public insert(key: T) {
        if (this._root == null) { // 根节点为空
            this._root = new Node<T>(key);
        } else { // 插入到非根节点处需要比较大小才能插入
            this.insertNode(this._root, key);
        }
    }
    /**
     * 插入一个节点的左侧还是右侧，用比较函数来比较
     */
    protected insertNode(node: Node<T>, key: T) {
        if (this._compareFn(key, node.key) === Compare.LESS_THAN) { // 第一个参数小于第二个参数
            if (node.left == null) {
                node.left = new Node<T>(key);
            } else {
                this.insertNode(node.left, key);
            }
        } else {
            if (node.right == null) {
                node.right = new Node<T>(key);
            } else {
                this.insertNode(node.right, key);
            }
        }
    }
    /**
     * 返回根节点
     */
    public getRoot() {
        return this._root;
    }
    /**
     * 在树中查找一个键。如果节点存在，则返回true，否则返回false
     */
    public search(key: T): boolean {
        return this.searchNode(this._root, key);
    }
    /**
     * 判断当前节点是否与key相等，如果key小于node.key就向左边迭代查找，大于就向右边查找，相等就返回
     */
    private searchNode(node: Node<T>, key: T): boolean {
        if (node == null) {
            return false;
        }
        if (this._compareFn(key, node.key) === Compare.LESS_THAN) { // key比这个node的key小就往左边走
            this.searchNode(node.left, key);
        } else if (this._compareFn(key, node.key) === Compare.BIGGER_THAN) { // key比这个node的key大就往右边走
            this.searchNode(node.right, key);
        }
        return true; // 直到相同就会返回true
    }
    /**
     * 通过中序遍历方式遍历所有节点
     */
    public inOrderTraverse(callBack: Function) {
        this.inOrderTraverseNode(this._root, callBack);
    }
    /**
     * 中序遍历
     */
    private inOrderTraverseNode(node: Node<T>, callBack: Function) {
        if (node != null) {
            this.inOrderTraverseNode(node.left, callBack);
            callBack(node); // 在父节点就调用
            this.inOrderTraverseNode(node.right, callBack);
        }
    }
    /**
     * 通过先序遍历方式遍历所有节点
     */
    public preOrderTraverse(callBack: Function) {
        this.preOrderTraverseNode(this._root, callBack);
    }
    /**
     * 先序遍历
     */
    private preOrderTraverseNode(node: Node<T>, callBack: Function) {
        if (node != null) {
            callBack(node); // 在左节点之前就调用
            this.preOrderTraverseNode(node.left, callBack);
            this.preOrderTraverseNode(node.right, callBack);
        }
    }
    /**
     * 通过后序遍历方式遍历所有节点
     */
    public postOrderTraverse(callBack: Function) {
        this.postOrderTraverseNode(this._root, callBack);
    }
    /**
     * 后序遍历
     */
    private postOrderTraverseNode(node: Node<T>, callBack: Function) {
        if (node != null) {
            this.postOrderTraverseNode(node.left, callBack);
            this.postOrderTraverseNode(node.right, callBack);
            callBack(node); // 在右节点之后就调用
        }
    }
    /**
     * 二叉搜索树的最小值
     */
    public min(): Node<T> {
        return this.minNode(this._root);
    }
    /**
     *  一直往左搜索找最小值
     */
    protected minNode(node: Node<T>): Node<T> {
        let current: Node<T> = node;
        while (current != null && current.left != null) {
            current = current.left;
        }
        return current;
    }
    /**
     * 二叉搜索树的最大值
     */
    public max(): Node<T> {
        return this.maxNode(this._root);
    }
    /**
     * 一直往右搜索找最大值
     */
    protected maxNode(node: Node<T>): Node<T> {
        let current: Node<T> = node;
        while (current != null && current.right != null) {
            current = current.right;
        }
        return current;
    }
    /**
     * 从移除二叉搜索树中的删除一项
     */
    public remove(key: T) {
        this._root = this.removeNode(this._root, key); // 更新根节点
    }
    /**
     * 删除的这项，要考虑它的子节点
     * 如果它的左侧和右侧子节点同时存在就要考虑用谁来替代它原来的位置
     * 目前按照常理，找它后方最接近它的项来替代它的位置，并把“被用来替代的项”也要用removeNode删除
     */
    protected removeNode(node: Node<T>, key: T): Node<T> {
        if (node == null) {
            return null;
        }
        if (this._compareFn(key, node.key) === Compare.LESS_THAN) { // key比这个node的key小就往左边走
            node.left = this.removeNode(node.left, key); // 左侧子节点可能会变化，更新左侧子节点的引用（指针）
            return node; // 更新父节点的引用（指针）
        } else if (this._compareFn(key, node.key) === Compare.BIGGER_THAN) { // key比这个node的key大就往右边走
            node.right = this.removeNode(node.right, key); // 右侧子节点可能会变化，更新右侧子节点的引用（指针）
            return node; // 更新父节点的引用（指针）
        } else { // 相等
            // 没有左右侧子节点，直接删除
            if (node.right == null && node.left == null) {
                node = null;
                return node; // 更新父节点的引用（指针）
            }
            if (node.right == null) { // 没有右侧子节点，而有左侧子节点，那么将左侧子节点替代它
                node = node.left;
                return node; // 更新父节点的引用（指针）
            } else if (node.left == null) { // 没有左侧子节点，而有右侧子节点，那么将右侧子节点替代它
                node = node.right;
                return node; // 更新父节点的引用（指针）
            }
            /*
             * 最特殊的情况，它有左侧子节点也有右侧子节点，删除它的话要选择合适的值替代它
             * 删除一个值一般都是从后面寻找最接近它的项，在二叉搜索树中最接近节点的项就是它右侧节点中最小的那个
             * 替代时，那个“被用来替代的项”也要删除，相当于用removeNode来迭代删除“被用来替代的项”
             */
            const aux: Node<T> = this.minNode(node.right);
            node.key = aux.key; // 先替换这个值，下一步去删除引用
            node.right = this.removeNode(node.right, aux.key); // 从右侧子节点开始删除那个“被用来替代的项”，并更新
            return node; // 更新父节点的引用（指针）
        }
    }
}
